﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using GenericGA.reader.regex;

namespace GenericGA.reader.tree
{
    /// <summary>
    /// A set of rules for describing how nodes in a tree are to be connected together in order to read trees.
    /// Trees which are generated will have a depth, which is defined as the maximum number of connections from the root to the leafs. In order to limit the size of the trees which are read, a maximum depth is to be provided. To limit the depth of the generated trees, this class will find the minimum depth needed to go from each child group of each node to all leaves. This will enable the tree generation to select children to use for the next level so that the maximum depth is never exceeded.
    /// In order to make the class as generic as possible, the nodes are generated using INodeFactory objects which is are factory objects that return nodes provided their children and a reader object. In this class, all nodes are described using their corresponding factory objects which will then be called in order to generate the actual node objects.
    /// </summary>
    /// <typeparam name="N">The super type of each node.</typeparam>
    public class Rules <N> where N : class
    {

        /// <summary>
        /// A class which joins together child nodes of a node with their collective minimum depth.
        /// </summary>
        private class Children
        {

            /// <summary>
            /// List of child nodes.
            /// </summary>
            public List<INodeFactory<N>> nodes;

            /// <summary>
            /// The collective minimum depth of these nodes.
            /// </summary>
            public int minDepth;

            /// <summary>
            /// Constructor which assigns the minimum depth to -1 in order to know if it has been eventually assigned or not.
            /// </summary>
            /// <param name="nodes">The child nodes.</param>
            public Children(List<INodeFactory<N>> nodes)
            {
                this.nodes = nodes;
                this.minDepth = -1;
            }

        }

        /// <summary>
        /// A class which joins together root nodes with their minimum depth.
        /// </summary>
        private class Root
        {
            
            /// <summary>
            /// The root node.
            /// </summary>
            public INodeFactory<N> root;

            /// <summary>
            /// The minimum depth the tree must be in order to be complete.
            /// </summary>
            public int minDepth;

            /// <summary>
            /// Constructor which assigns the minimum depth to -1 in order to know if it has been eventually assigned or not.
            /// </summary>
            /// <param name="root">The root node.</param>
            public Root(INodeFactory<N> root)
            {
                this.root = root;
                this.minDepth = -1;
            }

        }

        /// <summary>
        /// The minimum of the minimum depth of each root.
        /// </summary>
        private readonly int minRootDepth;

        /// <summary>
        /// A list of possible roots to use.
        /// </summary>
        private readonly List<Root> possibleRoots;

        /// <summary>
        /// A dictionary of node - children pairs.
        /// </summary>
        private readonly Dictionary<INodeFactory<N>, List<Children>> possibleChildren;

        /// <summary>
        /// A getter for the minimum depth the tree can be. Hence when reading a tree, the maximum depth provided must be greater than this number.
        /// </summary>
        public int MinTreeDepth
        {
            get
            {
                return minRootDepth;
            }
        }
        
        /// <summary>
        /// Constructor which checks and prepares rules for use.
        /// Throws:
        ///     CircularRulesException if there are children which never lead to a complete tree but just repeat back to their ancestors
        ///     IncompleteRulesException if there are nodes which are used as children but which don't have any children defined for them
        ///     UnreachableRulesException if there are nodes which are defined to have children but which can never be reached from the given roots
        ///     UndefinedRootException if there are roots which are not defined in the rules
        /// Notice that these exceptions could be thrown because of an inconsistent hash value returned by the INodeFactory objects. Performance of the algorithms used depends on the correct implementation of the GetHashValue methods of these objects.
        /// </summary>
        /// <param name="possibleRoots">Array of roots which the tree can start from.</param>
        /// <param name="rules">The rules which describe what can be connected to each node.</param>
        public Rules(INodeFactory<N>[] possibleRoots, params Rule<N>[] rules)
        {
            //Create dictionary of possible children for each node
            possibleChildren = new Dictionary<INodeFactory<N>, List<Children>>();
            foreach (Rule<N> rule in rules)
            {
                //Since different rules may have same node, might as well add each rule to what is already in possibleChildren[rule.node]
                if (!this.possibleChildren.ContainsKey(rule.Node))
                {
                    this.possibleChildren.Add(rule.Node, new List<Children>());
                }

                foreach (List<INodeFactory<N>> children in rule.ChildrenPattern.Enumerate())
                {
                    this.possibleChildren[rule.Node].Add(new Children(children));
                }
            }

            //Get all nodes mentioned in the rules
            HashSet<INodeFactory<N>> allNodes = new HashSet<INodeFactory<N>>();
            foreach (INodeFactory<N> node in possibleChildren.Keys)
            {
                foreach (Children children in possibleChildren[node])
                {
                    allNodes.Add(node);
                    allNodes.UnionWith(children.nodes);
                }
            }

            //Check that every node has a rule describing its children
            if (possibleChildren.Keys.Count != allNodes.Count)
            {
                throw new IncompleteRulesException("There are no rules specifying the children of some nodes. If node is a leaf node then specify this by making its children be the empty regular expression.");
            }

            //Check that every root is defined in the rules
            if (!possibleRoots.All<INodeFactory<N>>(root => allNodes.Contains(root)))
            {
                throw new UndefinedRootException("There are roots which are not defined in the rules.");
            }

            //Check that every node is a descendent of some root
            HashSet<INodeFactory<N>> reachableNodes = new HashSet<INodeFactory<N>>();
            foreach (INodeFactory<N> root in possibleRoots)
            {
                GetReachableNodes(root, reachableNodes);
            }
            if (reachableNodes.Count != allNodes.Count)
            {
                throw new UnreachableRulesException("Not all nodes are reachable from some root.");
            }

            //Get the minimum depths of each child group in the rules and check if the rules are circular
            foreach (INodeFactory<N> node in possibleChildren.Keys)
            {
                foreach (Children children in possibleChildren[node])
                {
                    try
                    {
                        children.minDepth = GetMinDepth(children, new HashSet<INodeFactory<N>>());
                    }
                    catch (CircularRulesException)
                    {
                        throw new CircularRulesException("At least one rule never leads to a complete tree because all the descendants it produces lead back to it. This rule is " + node + " -> " + children.nodes + ".");
                    }
                }
            }

            //Get the minimum depth the tree should be in order to be able to use at least one root
            this.possibleRoots = new List<Root>(new Root[possibleRoots.Length]);
            minRootDepth = int.MaxValue;
            for (int i = 0; i < possibleRoots.Length; i++)
            {
                INodeFactory<N> root = possibleRoots[i];

                this.possibleRoots[i] = new Root(root);
                int minDepth = int.MaxValue; //For performance reasons a temporary variable was used in order to determine the minimal depth which will then be assigned to the Root object after computation
                foreach (Children children in possibleChildren[root])
                {
                    if (children.minDepth < minDepth)
                    {
                        minDepth = children.minDepth;

                        if (minDepth < minRootDepth)
                        {
                            minRootDepth = minDepth;
                        }
                    }
                }
                this.possibleRoots[i].minDepth = minDepth;
            }
        }

        /// <summary>
        /// Recursively find the minimum depth needed to make a set of child nodes all lead to leaf nodes.
        /// </summary>
        /// <param name="children">The set of child nodes.</param>
        /// <param name="ancestors">A set of ancestors nodes that were traversed prior to arriving to these child nodes. This is to avoid retraversing the same paths and also to detect circular rules.</param>
        /// <returns>The minimum depth.</returns>
        private int GetMinDepth(Children children, HashSet<INodeFactory<N>> ancestors)
        {
            //If any of the child nodes is an ancestor of the traversal then throw an internal exception as rule was a dead end
            if (children.nodes.Any<INodeFactory<N>>(ancestors.Contains<INodeFactory<N>>))
            {
                throw new CircularRulesException();
            }
            
            //Base case: If there is nothing left to traverse then minimum depth is zero
            else if (children.nodes.Count == 0)
            {
                return 0;
            }

            //Recursive case: Find the minimum depth of each child and return their maximum
            else
            {
                //Find the maximum depth of the children
                int max = int.MinValue;
                foreach (INodeFactory<N> child in children.nodes)
                {
                    //The depth of each child is the minimum depth of each child's children
                    int min = int.MaxValue;
                    ancestors.Add(child); //Add this child as an ancestor
                    foreach (Children grandChildren in possibleChildren[child])
                    {
                        try
                        {
                            int tmp = GetMinDepth(grandChildren, ancestors);
                            if (tmp < min)
                            {
                                min = tmp;
                            }
                        }
                        catch (CircularRulesException) {} //If this rule leads to a dead end then ignore its depth
                    }
                    ancestors.Remove(child); //Remove this child as an ancestor

                    //If all descendants of this child lead to an ancestor then throw an internal exception
                    if (min == int.MaxValue)
                    {
                        throw new CircularRulesException();
                    }

                    if (min > max)
                    {
                        max = min;
                    }
                }

                //Return the maximum depth + 1, incremented at the end for performance reasons
                return max + 1;
            }
        }

        /// <summary>
        /// Recursively find which nodes are reachable from a root node using the rules.
        /// </summary>
        /// <param name="root">The root node to start searching from.</param>
        /// <param name="reachableNodes">A set of nodes which are reachable from the node. This is kept as a mutable parameter rather than returned so that nodes which were already traversed will be avoided and hence improve performance. This should start as an empty set.</param>
        private void GetReachableNodes(INodeFactory<N> root, HashSet<INodeFactory<N>> reachableNodes)
        {
            //If root has already been traversed then skip it
            if (reachableNodes.Contains<INodeFactory<N>>(root))
            {
                return;
            }

            //Else, add root to reachable nodes and check its descendents
            else
            {
                reachableNodes.Add(root);
                foreach (Children children in possibleChildren[root])
                {
                    foreach (INodeFactory<N> child in children.nodes)
                    {
                        GetReachableNodes(child, reachableNodes);
                    }
                }
            }
        }

        /// <summary>
        /// Get the children of a node which can be used given a depth limitation.
        /// </summary>
        /// <param name="node">The node the children belong to.</param>
        /// <param name="maxDepth">The maximum depth which can be used.</param>
        /// <returns>The list of possible children.</returns>
        private List<Children> GetPossibleChildren(INodeFactory<N> node, int maxDepth)
        {
            return possibleChildren[node].FindAll(children => (children.minDepth <= maxDepth));
        }

        /// <summary>
        /// Get the root nodes to start tree generation which can be used given a depth limitation.
        /// </summary>
        /// <param name="maxDepth">The maximum depth which can be used.</param>
        /// <returns>The list of possible roots.</returns>
        private List<Root> GetPossibleRoots(int maxDepth)
        {
            return possibleRoots.FindAll(root => (root.minDepth <= maxDepth));
        }

        /// <summary>
        /// Main method to generate a tree given a reader object.
        /// </summary>
        /// <param name="reader">Reader object to determine how to generate the tree.</param>
        /// <param name="maxDepth">The maximum depth the tree is to have.</param>
        /// <returns>The tree, or rather the root node which is connected to the rest of the sub trees.</returns>
        public N Generate(Reader reader, int maxDepth)
        {
            if (maxDepth < minRootDepth)
            {
                return null;
            }

            INodeFactory<N> root = reader.ReadElem<Root>(GetPossibleRoots(maxDepth)).root;
            return Generate(root, reader, maxDepth);
        }

        /// <summary>
        /// Helper method for the Generate method in order to recursively generate trees.
        /// </summary>
        /// <param name="root">The root object to start generating the tree from.</param>
        /// <param name="reader">Reader object to determine how to generate the tree.</param>
        /// <param name="maxDepth">The maximum depth the tree is to have.</param>
        /// <returns>The tree, or rather the root node which is connected to the rest of the sub trees.</returns>
        private N Generate(INodeFactory<N> root, Reader reader, int maxDepth)
        {
            //Determine the children to use to connect to the root
            Children children = reader.ReadElem<Children>(GetPossibleChildren(root, maxDepth));
            //Call the factory method of the root to create a root node which is connected to the children where each child node is created the same way recursively
            return root.CreateNode(children.nodes.ConvertAll<N>(
                delegate(INodeFactory<N> i)
                {
                    return Generate(i, reader, maxDepth - 1);
                }
            ), reader);
        }

    }
}
